COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00011 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\line{\sevenrm a39.tex[154,mps] \today\hfill}
\baselineskip 14pt

\bigskip
\line{\bf The Relation Between Stacks and Parentheses\hfil}

Let $\Sigma$ be an alphabet, $\Sigma↑{\ast}$ the strings over~$\Sigma$.
All strings can be formed by starting with~$\Lambda$ and appending
characters on one end. We assume it's the right end, but all the results
that follow work for the left end as well. We use $S↓a(x)$, where
$a\in\Sigma$, $x\in\Sigma↑{\ast}$, to mean the string~$x$ with character~$a$
appended. The following are the {\sl Peano axioms\/} for strings:

\disleft 20pt:(1):
$\Lambda\in\Sigma↑{\ast}$.

\disleft 20pt:(2):
If $x\in\Sigma↑{\ast}$ and $a\in\Sigma$, then $S↓a(x)\in\Sigma↑{\ast}$.

\disleft 20pt:(3):
(Induction axiom) If $\Lambda$ has a property $P$, and if $S↓a(x)$ has 
property $P$ whenever $x$ does, then every string
in~$\Sigma↑{\ast}$ has the property. In a formula,
$$\bigl(P(\Lambda)\wedge((\forall x\in\Sigma↑{\ast},a\in\Sigma)
P(x)⊃P(S↓a(x)))\bigr)⊃(\forall x\in\Sigma↑{\ast})P(x)\,.$$

\disleft 20pt:(4):
$S↓a(x)≠\Lambda$.

\disleft 20pt:(5):
$S↓a(x)=S↓b(y)$ implies that $a=b$ and $x=y$.

\proclaim Theorem. Every string in $\Sigma↑{\ast}$ is either $\Lambda$
or $S↓a(x)$ for some~$a$ and~$x$.

\noindent{\bf Proof.} Let $P(y)$ be the property $y=\Lambda\vee
(\exists x,a)y=S↓a(x)$. An easy application of axiom~3 shows that
$y\in\Sigma↑{\ast}⊃P(y)$.

\medskip
Concatenation is defined by

\disleft 20pt:(1):
$x\otimes\Lambda =x$.

\disleft 20pt:(2):
$x\otimes S↓a(y)=S↓a(x\otimes y)$.

The following drills lead the reader to construct a proof of a major
theorem connecting context-free grammars, stacks, and parentheses.
\smallskip

{\smallskip\rmn\noindent
\noindent{\bf Drill \#1.} Use the Peano axioms to show that the above determine
$x\otimes y$ uniquely
for all~$x$ and~$y$.
\smallskip}

{\smallskip\rmn\noindent
\noindent{\bf Drill \#2.} Use the Peano axioms to show $\Lambda\otimes x=x$ 
and
$(x\otimes y)\otimes z=x\otimes (y\otimes z)$.
\smallskip}

A stack is a string; a stack with alphabet $\Sigma$ is a string in~$\Sigma↑{\ast}$.
Let the relation $\{\,\langle x,S↓a(x)\rangle\mid$\break 
$x\in\Sigma↑{\ast}\,\}$ be
called push~$a$, and the converse relation pop~$a$.

{\smallskip\rmn\noindent
\noindent{\bf Drill \#3.} Show push $a$ is a function.
\smallskip}

{\smallskip\rmn\noindent
\noindent{\bf Drill \#4.} Show pop $a$ is a partial function, defined on~$u$ iff
$u=S↓a(v)$ for some~$v$.
\smallskip}

{\smallskip\rmn\noindent
\noindent{\bf Drill \#5.} Show ${\rm push}\;a\,\circ\,{\rm pop}\; 
a=I↓{\Sigma↑{\ast}}$, the identity relation on strings over $\Sigma$.
\smallskip}

{\smallskip\rmn\noindent
\noindent{\bf Drill \#6.} Show ${\rm push}\;a\,\circ\,{\rm pop}\; b=\emptyset$ 
if $b≠a$.
\smallskip}

Define a language $L$ of nested parentheses by:

\disleft 20pt:(1):
$\Lambda\in L$.

\disleft 20pt:(2):
If $x\in L$, so are $(x)$ and $[x]$.

\disleft 20pt:(3):
If $x,y\in L$, so is $xy$.

\disleft 20pt:(4):
$L$ is the smallest language with the above properties. In other words, 
(1), (2), and (3) allow proofs by induction about~$L$.

Define a CFG $G↓1$ with productions
$$E→\Lambda\mid(E)E\mid [E]E\,.$$

{\smallskip\rmn\noindent
\noindent{\bf Drill \#7.} Prove by induction that $L=L↓{G↓1}$.
\smallskip}

We shall call this language $L↓{(\,)[\,]}$. If we substitute push~$a$ for~$($,
pop~$a$ for~$)$, push~$b$ for~$[$, and pop~$b$ for~$]$ in the above grammar~$G↓1$,
we get the grammar~$G↓2$:
$$F→\Lambda\mid\;{\rm push}\; a\,F\;{\rm pop}\; a\,F\mid\,{\rm push}\;
b\,F\;{\rm pop}\; b\,F\,.$$

{\smallskip\rmn\noindent
{\bf Drill \#8.} Prove by induction that every sentence in $L↓{G↓2}$ names
a relation equal to $I↓{\Sigma↑{\ast}}$. (By convention, $\Lambda$
names~$I↓{\Sigma}$.)
\smallskip}

{\smallskip\rmn\noindent
{\bf Drill \#9.} Show that any sequence of pushes and pops that changes the empty
stack to the empty stack is a sentence in the above grammar.
\smallskip}

It follows that a sequence the sequence of pushes and props that leaves the
empty stack unchanged leaves every stack unchanged, and that the
sequence of stack operations in a standardized
PDM computation is an (encoded) string in $L↓{(\,)[\,]}$.

{\smallskip\rmn\noindent
{\bf Drill \#10.} Take a labeled graph form of a standardized PDM. 
Prove that a string $x$ is a computation of that PDM if and only if:
\smallskip}

\display 40pt:{\rmn (1)}:
{\rmn $x$ is a labeled path through the graph.}

\display 40pt:{\rmn (2)}:
{\rmn Omitting all symbols except push $a$, pop $a$, push $b$, pop $b$ from $x$
gives a sentence in~$G↓2$.}

\smallskip
\display 20pt::
{\rmn
(The labeled graph form labels each arc with operations like read~$a$,
write~$b$, push~$c$, pop~$d$, etc. A~labeled path is 
$q↓0l↓1q↓1l↓2q↓2\ldots$, where $q↓{i-1}l↓iq↓i$ is a labeled arc
of the graph.)
}

{\smallskip\rmn\noindent
{\bf Drill \#11.} Show that if $M$ is a PDM, there is a GSM, $M'$, that maps
$L↓{(\,)[\,]}$ onto the set of computations of~$M$. That is, if~$M'$ has 
input-output relation~$R$,
the set of computations of~$M$ is $L↓{(\,)[\,]}\circ R$.
\smallskip}

{\smallskip\rmn\noindent
{\bf Drill \#12.} Show that the set of strings accepted by a PDM is the image of
$L↓{(\,)[\,]}$ under transductions by a~GSM (a~GSM mapping).
\smallskip}

\proclaim Theorem. The CFLs are the images of $L↓{(\,)[\,]}$ under GSM mappings.

\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
May 2, 1986.

Revised date; May 9, 1988
%subsequently revised.

\bye